package com.LeeCode;

import java.util.HashMap;

/**
 * 字母组合迭代器
 */

public class Code1286 {
    public static void main(String[] args) {
        CombinationIterator iterator = new Code1286().new CombinationIterator("ahijp", 2);
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }

    class CombinationIterator {

        private int combinationLength, total;
        private StringBuilder currentCombination;
        private HashMap<Character, Integer> map;
        private char[] chars;

        public CombinationIterator(String characters, int combinationLength) {
            this.combinationLength = combinationLength;
            this.total = characters.length();
            map = new HashMap<>();
            this.chars = characters.toCharArray();
            for (int i = 0; i < characters.length(); i++) {
                map.put(this.chars[i], i);
            }
        }

        public String next() {
            if (currentCombination == null) {
                currentCombination = new StringBuilder();
                for (int i = 0; i < combinationLength; i++) {
                    currentCombination.append(chars[i]);
                }
                return currentCombination.toString();
            }
            for (int i = combinationLength - 1; i >= 0; i--) {
                int index = map.get(currentCombination.charAt(i));
                if (index != total - combinationLength + i) {
                    index++;
                    currentCombination.setCharAt(i, chars[index]);
                    for (int j = i + 1; j < combinationLength; j++) {
                        currentCombination.setCharAt(j, chars[++index]);
                    }
                    return currentCombination.toString();
                }
            }
            return null;
        }

        public boolean hasNext() {
            if (currentCombination == null) return true;
            int index = map.get(currentCombination.charAt(0));
            return index != total - combinationLength;
        }
    }
}
